1. Technical Field
The present invention pertains to communication systems. In particular, the present invention pertains to a wireless communication system utilizing network topology information to form clusters for data transmission by a minimal quantity of hops and without regard to initial start times of network nodes. In addition, the present invention pertains to a wireless communication system employing cluster formation to form a multiple tier network architecture and facilitate transmission of node link status messages with reduced protocol overhead traffic.
2. Discussion of Related Art
Generally, certain wireless networks, such as a cellular network, commonly utilize a relay station to forward a message from a mobile cellular unit to a desired destination. The relay station is typically a fixed base station where each mobile unit transmits an outgoing message directly to the base station (e.g., the base station is generally within one hop from the mobile units) for forwarding through a public telephone network to the desired destination. Ad hoc wireless networks (e.g., dynamic wireless networks without any routing infrastructure) are typically employed for military and personal communication applications. These types of networks do not include fixed base stations, but rather employ nodes that each dynamically determine a relay type network node to route traffic. Thus, the ad hoc network node is provided with a difficult task of determining a routing path for data transmission. Since several hops are typically required to facilitate communications, the cellular scheme described above is insufficient for ad hoc networks.
The related art has attempted to overcome the aforementioned problem by providing flat and hierarchical network architectures for data routing. In particular, the flat architecture basically includes a single tier of network nodes in communication with each other. The flat architecture performs adequately with small scale networks, however, overhead traffic increases rapidly and exceeds network capacity in response to increasing network size. The hierarchal architecture basically arranges a network into plural tiers or hierarchical levels. The first tier typically includes clusters or cells each including a plurality of communication nodes or cluster members. One node within each cluster is designated as the cluster head and has full connectivity to corresponding member nodes. The second tier includes a backbone network formed of the cluster head nodes to enable communications between different clusters (e.g., for data transmitted over greater distances). Thus, the first network tier represents each network node, while the second network tier represents cluster head nodes. In operation, a network member node initially transmits a message to its corresponding cluster head node which subsequently forwards the message through the backbone network (e.g., through plural hops of cluster head nodes) to a destination cluster head node associated with a destination member node. Since full connectivity exists between each cluster head node and its corresponding member nodes, the destination cluster head node transmits the message to the corresponding destination member node. This type of architecture is typically employed in communication networks for military applications.
The formation of clusters and designation of cluster head nodes is generally performed dynamically within the exemplary hierarchical network, while the network employs a routing protocol to facilitate communications within the network. The routing protocol is preferably a link-state type of protocol that is implemented on the backbone network (e.g., by the cluster head nodes). The cluster head nodes each include a database that has information enabling the cluster head nodes to determine appropriate paths for routing messages. In particular, each head node constructs a routing table to determine a successive link to transmit a message from that node toward a destination head node. This is accomplished by transmitting or flooding routing information from each head node database among cluster head nodes to synchronize those databases. In order to ensure receipt of database information, a receiving head node transmits an acknowledgment message to a source head node transmitting the database information. If an acknowledgment message is not received within a predetermined time interval, the database information is re-transmitted to the network head nodes that have not acknowledged receipt of the database information. In addition, each network node (e.g., cluster head and member nodes) periodically broadcasts a beacon type or node status packet in accordance with the routing protocol. This packet basically advertises the presence of a node within the network, and is typically utilized by cluster head nodes for “keep alive” and neighbor discovery purposes.
In order to facilitate internet routing or routing between the hierarchical and other external networks (e.g., the Internet), a modified version of the conventional Open Shortest Path First (OSPF) Protocol may be employed. The OSPF protocol is basically a routing protocol employed for Internet Protocol (IP) type networks, while the modified protocol or Radio Open Shortest Path First (ROSPF) protocol is similar to OSPF, but is adapted for use with radio or wireless networks. For examples of implementation of the OSPF Protocol, reference is made to RFC 1583, Moy, “OSPF Version 2,” March 1994, the disclosure of which is incorporated herein by reference in its entirety.
Routing is accomplished in the OSPF protocol by each network node having a routing database containing information related to network topology (e.g., links between network nodes). The routing database is utilized by each node to determine a path for transmitting a message to a destination site. The routing databases are updated by exchanging Link-State Advertisement (LSA) packets between neighboring nodes. These packets generally include information related to current links of network nodes and are typically transferred periodically and/or in the event of a modification to the network topology. The OSPF protocol designates a particular router to flood LSA packets to neighbors in broadcast type networks, while LSA packets are transmitted via point-to-point within non-broadcast type networks. The ROSPF protocol employed by the hierarchical network described above is similar to the OSPF protocol and exchanges LSA type packets between neighbors (e.g., cluster head and member nodes) to synchronize routing databases as described above.
The hierarchical architecture may provide significant reduction in routing overhead traffic in relation to the flat architecture depending upon the quantity of cluster head nodes employed. Accordingly, the related art provides several clustering techniques to arrange a network into a hierarchical architecture. Initially, a cluster head node may be utilized to replace the functionality of a cellular network base station and basically serves as a pseudo base station for data traffic within a corresponding cluster. A technique of the related art for cluster head designation and subsequent cluster formation includes determining clusters based on identifiers (e.g., identification codes or numbers) of network nodes. This technique basically designates a network node having a lowest (e.g., or greatest) node identifier as a cluster head. The related art has expanded this technique to utilize a node identifier or a degree of node connectivity to designate a cluster head node, and has further modified the technique to employ interconnected non-overlapping clusters to cover an entire network.
In addition, clustering techniques have been employed for military communication applications and provide a basis for routing protocols. One such technique determines cluster head nodes in accordance with initial random start times of network nodes. Basically, each network node may initiate power or start up at various times, thereby providing a generally random node initiation sequence. A network node is designated as a cluster head node in response to node initiation and determining the absence of neighboring nodes. Thus, nodes having early initiation times tend to be designated as cluster head nodes by this technique. The routing protocol commonly designates cluster head nodes and forms clusters based on network node identifiers (e.g., lowest node identifier is designated as a head node) and certain designation rules.
The clustering techniques of the related art suffer from several disadvantages. In particular, the above clustering techniques generally utilize simple criteria to dynamically designate a cluster head without employing network topology information. In particular, the techniques typically designate a cluster head node based on lowest or greatest node identifier. However, this may result in no direct links between cluster head nodes, thereby requiring additional gateway type nodes (e.g., nodes having communications with two cluster head nodes) to facilitate communication between clusters and increasing the quantity of hops required for communication. The approach according to node random start times may designate a significant quantity of nodes as cluster head nodes, where the designations are typically not optimal selections for a network configuration. Further, this cluster formation technique depends upon the particular sequence of node initiation, thereby enabling particular initiation sequences to facilitate a formation failure. Moreover, the above clustering techniques complicate determination of an appropriate interval between node status packet transmissions. When the interval is set to a value below an acceptable range, large scale networks may become congested. Conversely, if the interval is set to a value above an acceptable range, an extensive time interval is required to complete cluster formation. In addition, the above clustering techniques typically require the initial start times of network nodes to be spaced apart a sufficient interval in order to avoid network failure as the quantity of nodes within the network increases.
With respect to the network architectures for data routing, the flat architecture performs adequately for small scale networks, but as network size increases, the flat network rapidly becomes congested since overhead traffic increases exponentially with network size. The hierarchical architecture reduces overhead traffic relative to the flat network architecture, however, this reduction is insufficient when the network employs on the order of several hundred nodes, thereby limiting application of the routing protocol. Although reliability of flooding node database information throughout a network is enhanced by transmission of acknowledgment messages, these messages increase overhead traffic, thereby degrading network performance.
The present invention overcomes the aforementioned problems by utilizing network topology information to identify network nodes crucial for relaying traffic. The identified nodes are designated as cluster head nodes, while remaining nodes are designated as member nodes. Since cluster head nodes basically serve as relay nodes, the present invention removes the need for gateway type nodes. In other words, the present invention designates a minimum quantity of network nodes as cluster head nodes to achieve connectivity among the nodes. Since the present invention employs a deterministic approach, cluster formation remains substantially the same independently of the initial start-up sequence of network nodes. Further, the designation of cluster head nodes by the present invention is optimal since the designated nodes are crucial for relaying network traffic. Moreover, since the quantity of cluster head nodes that may facilitate communications depends upon the interval between node status packet transmissions, the present invention adaptively adjusts that interval to subsequently facilitate cluster formation independent of network size and varying start times of network nodes.
In addition, the present invention employs a cluster formation technique to form a three tier hierarchical network in order to apply the routing protocol to large scale networks. The cluster formation technique is applied to the cluster head nodes or backbone network to form third tier clusters. Nodes within the third tier distribute routing information from head node databases to reduce overhead traffic, while head nodes within the second tier are utilized for data routing. Further, the present invention reduces overhead traffic by eliminating transmission of acknowledgment messages in response to receipt of the database information. Basically, the present invention examines head node databases and requests third tier nodes to supply missing information. Thus, the present invention only sends request messages in response to receipt of the database information and discovering missing data within head node databases, thereby significantly reducing overhead traffic.